package com.problem.stack;

import java.util.Stack;

/**
 * 20
 * https://leetcode-cn.com/problems/valid-parentheses/
 */
public class ValidParentheses {
    //给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
    //
    //有效字符串需满足：
    //
    //左括号必须用相同类型的右括号闭合。
    //左括号必须以正确的顺序闭合。
    //注意空字符串可被认为是有效字符串。
    //
    //示例 1:
    //
    //输入: "()"
    //输出: true
    //示例 2:
    //
    //输入: "()[]{}"
    //输出: true
    //示例 3:
    //
    //输入: "(]"
    //输出: false

    //示例 4:
    //
    //    输入: "([)]"
    //    输出: false
    //    示例 5:
    //
    //    输入: "{[]}"
    //    输出: true

    public boolean isValid(String s) {
        Stack<String> stack = new Stack<>();
        if (s == null || s.length()%2==1) {
            return false;
        }
        for (int i=0;i<s.length();i++) {
            if ("(".equals(String.valueOf(s.charAt(i))) ||
                    "[".equals(String.valueOf(s.charAt(i))) || "{".equals(String.valueOf(s.charAt(i)))) {
                stack.push(String.valueOf(s.charAt(i)));
            } else {
                if (stack.empty() || !match(stack.pop(),String.valueOf(s.charAt(i)))) {
                    return false;
                }
            }
        }
        if (stack.empty()) {
            return true;
        }
        return false;
    }

    private boolean match(String a, String b) {
        return "(".equals(a) && ")".equals(b) ||
                "[".equals(a) && "]".equals(b) ||
                "{".equals(a) && "}".equals(b);

    }


    public static void main(String[] args) {
        ValidParentheses vp = new ValidParentheses();
        System.out.println(vp.isValid("()"));
        System.out.println(vp.isValid("([)]"));
        System.out.println(vp.isValid("()[]{}"));
        System.out.println(vp.isValid("(]"));
    }
}
